package 查找算法.跳跃查找;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 查找算法.跳跃查找
 * @ClassName: JumpSearch
 * @Author: zhouyihe
 * @Date: 2025/11/17 11:43
 * @Description: 跳跃查找
 * 优点:
 * 比线性查找更高效，时间复杂度为 O(√n)
 * 比二分查找更易于实现
 * 在链表等只能顺序访问的数据结构上有优势
 * 良好的内存局部性，更利于缓存命中
 * 缺点:
 * 时间复杂度不如二分查找的 O(log n)
 * 性能对步长的选择比较敏感
 * 必须是有序数组
 * 对于小数组，优势不明显
 * 针对频繁动态变化的数据结构，需要重新计算最优步长
 */
public class JumpSearch {
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;

        int step = (int) Math.floor(Math.sqrt(n));

        // 跳跃查找阶段
        int prev = 0;
        while (arr[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.floor(Math.sqrt(n));
            if (prev >= n) {
                return -1;  // 未找到元素
            }
        }

        // 线性查找阶段
        while (arr[prev] < target) {
            prev++;

            // 如果已到达下一步长或数组末尾，则未找到元素
            if (prev == Math.min(step, n)) {
                return -1;
            }
        }

        // 检查是否找到目标元素
        if (arr[prev] == target) {
            return prev;  // 返回元素索引
        }

        return -1;  // 未找到元素423
    }
}
